//----------------------------------------------------------------------矩阵
#define CC(a,i) memset(a,i,sizeof(a))
#define M 4
typedef long long LL;
struct matrix{
	int Mat[4][4];
	matrix(int a){
		CC(Mat,0);
		for(int i=0;i<M;i++)Mat[i][i]=a;
	}
	matrix(){matrix(1);}
	matrix(int x[][M]){memcpy(Mat,x,sizeof(Mat));}
	
	matrix operator*(matrix a)
	{
		matrix ret;
		for(int i=0;i<M;i++)
		for(int j=0;j<M;j++)
		{
			ret.Mat[i][j]=0;
			for(int k=0;k<M;k++)
				ret.Mat[i][j]+=Mat[i][k]*a.Mat[k][j];
			ret.Mat[i][j]%=2009;
		}
		return ret;
	}

	matrix operator^(LL pow)
	{
		matrix ret(1),tmp=*this;
		for(;pow;pow>>=1,tmp=tmp*tmp)
			if(pow&1)
				ret=ret*tmp;
		return ret;
	}

	void show()
	{
		for(int i=0;i<M;i++)
		{
			for(int j=0;j<M;j++)
				printf("%3d ",Mat[i][j]);
			puts("");
		}
	}
};
